package ch04;

import java.util.LinkedList;
/**
 * At first glance, it seems like using BFS is preferrable, however, DFS is also a good candidate.
 */
public class Ch4_4 {
    public static LinkedList<LinkedList<BinaryNode<Integer>>> nodesAtTheSameDepth_BFS(BinaryNode<Integer> node) {
	LinkedList<BinaryNode<Integer>> previous = new LinkedList<BinaryNode<Integer>>();
	LinkedList<LinkedList<BinaryNode<Integer>>> lists = new LinkedList<LinkedList<BinaryNode<Integer>>>();
	if (node != null) {
	    previous.add(node);
	}
	while (!previous.isEmpty()) {
	    lists.add(previous);
	    LinkedList<BinaryNode<Integer>> current = new LinkedList<BinaryNode<Integer>>();
	    for (BinaryNode<Integer> n: previous) {
		if (null != n.left) {
		    current.add(n.left);
		}
		if (null != n.right) {
		    current.add(n.right);
		}
	    }
	    previous = current;
	}
	return lists;
    }

    public static void nodesAtTheSameDepth_DFS(BinaryNode<Integer> node, int depth, LinkedList<LinkedList<BinaryNode<Integer>>> lists) {
	if (node == null) {
	    return;
	}
	if (lists.get(depth) == null) {
	    LinkedList<BinaryNode<Integer>> list = new LinkedList<BinaryNode<Integer>>();
	    lists.add(list);
	    list.add(node);
	}
	nodesAtTheSameDepth_DFS(node.left, depth + 1, lists);
	nodesAtTheSameDepth_DFS(node.right, depth + 1, lists);
    }

    public static void main(String[] args) {
	int limit = 100;
	int elements[] = new int[limit];
	for (int i = 0; i < limit; i++) {
	    elements[i] = i;
	}
	BinaryNode<Integer> node = new BinaryNode<Integer>();
	Ch4_3.createMinBst(elements, 0, elements.length - 1, node);

	//LinkedList<LinkedList<BinaryNode<Integer>>> lists = nodesAtTheSameDepth_BFS(node);
	LinkedList<LinkedList<BinaryNode<Integer>>> lists = new	LinkedList<LinkedList<BinaryNode<Integer>>>();
	nodesAtTheSameDepth_DFS(node, 0, lists);
	for (LinkedList<BinaryNode<Integer>> list: lists) {
	    for (BinaryNode<Integer> n: list) {
		System.out.print(n + " ");
	    }
	    System.out.println();
	}
    }
}
